/**
 * 路径初始化
 * @param {*} graph 路径，geojson,里面的线需要是Linestring，不能是MutilLineString
 * @param {*} options {precision:精度，小数位数，weightFn:权重函数}
 */
function Route(graph, options) {
    options = options || {};
    //this._precision = options.precision || 1e-5;
    this._precision = options.precision || 5;
    this._weightFn = options.weightFn || function defaultWeightFn(a, b) {
        return turf.distance(turf.point(a), turf.point(b));
    };
    this._keyFn = options.keyFn || function (c) {
        return c.join(',');
    };
    this._options = options;
    if (!graph.compactedVertices) {
        //原数据保存下来
        this._sourceGraph = graph;
        //构造图
        graph = this.prepare(graph, options)
    }

    this._graph = graph;

    if (Object.keys(this._graph.compactedVertices).filter(function (k) { return k !== 'edgeData'; }).length === 0) {
        throw new Error('Compacted graph contains no forks (topology has no intersections).');
    }
}

/**
 * 寻找路径
 * @param {*} start 
 * @param {*} finish 
 * @returns 
 */
Route.prototype.find = function (start, finish) {

    //起始点截取
    var startSnapped = turf.nearestPointOnLine(this._sourceGraph, start);
    var finishSnapped = turf.nearestPointOnLine(this._sourceGraph, finish);

    var startKey = this._keyFn(roundCoord(startSnapped.geometry.coordinates, this._precision));
    var finishKey = this._keyFn(roundCoord(finishSnapped.geometry.coordinates, this._precision));

    var insertStart = false, insertEnd = false;

    if (!this._graph.vertices[startKey]) {
        insertStart = this.insertVertice(startSnapped.geometry.coordinates);
    }

    if (!this._graph.vertices[finishKey]) {
        insertEnd = this.insertVertice(finishSnapped.geometry.coordinates);
    }
    
    var phantomStart = this.createPhantom(startKey);
    var phantomEnd = this.createPhantom(finishKey);

    if (!this._graph.vertices[startKey] || !this._graph.vertices[finishKey]) {
        return null;
    }
    var path = this.dijkstraCalc(this._graph.compactedVertices, startKey, finishKey);
    var result = null;
    if (path) {
        var weight = path[0];
        path = path[1];
        result = {
            path: path.reduce(function buildPath(cs, v, i, vs) {
                if (i > 0) {
                    cs = cs.concat(this._graph.compactedCoordinates[vs[i - 1]][v]);
                }

                return cs;
            }.bind(this), []).concat([this._graph.sourceVertices[finishKey]]),
            weight: weight,
            edgeDatas: this._graph.compactedEdges
                ? path.reduce(function buildEdgeData(eds, v, i, vs) {
                    if (i > 0) {
                        eds.push({
                            reducedEdge: this._graph.compactedEdges[vs[i - 1]][v]
                        });
                    }

                    return eds;
                }.bind(this), [])
                : undefined
        };
    }
    if (insertStart) {
        this.removeVertice(startSnapped.geometry.coordinates);
    }
    if (insertEnd) {
        this.removeVertice(finishSnapped.geometry.coordinates);
    }
    this.removePhantom(phantomStart);
    this.removePhantom(phantomEnd);
    return result;
}

/**
 * 插入节点
 * @param {Array} coord 
 */
Route.prototype.insertVertice = function (coord) {
    var point = turf.point(coord);
    var key = this._keyFn(roundCoord(coord, this._precision));
    var nearestLines = geoJsonFilterFeatures(this._sourceGraph, function (feature) {
        return turf.booleanPointOnLine(point, feature, { epsilon: 0.0000001 })
    });
    if (nearestLines.features.length > 0) {
        var nearestLine = nearestLines.features[0];
        var split = turf.lineSplit(nearestLine, point);
        if (split.features.length == 2) {
            var feature1 = split.features[0], feature2 = split.features[1];
            //插入节点，该节点前后节点信息
            var coord1 = feature1.geometry.coordinates[feature1.geometry.coordinates.length - 2], coord2 = feature2.geometry.coordinates[1];
            var key1 = this._keyFn(roundCoord(coord1, this._precision)), key2 = this._keyFn(roundCoord(coord2, this._precision));

            this._graph.vertices[key] = {};
            this._graph.vertices[key][key1] = this._weightFn(coord, coord1);
            this._graph.vertices[key][key2] = this._weightFn(coord, coord2);

            //关联节点
            this._graph.vertices[key1][key] = this._weightFn(coord, coord1);
            this._graph.vertices[key2][key] = this._weightFn(coord, coord2);

            delete this._graph.vertices[key1][key2];
            delete this._graph.vertices[key2][key1];

            this._graph.sourceVertices[key] = coord;

            return true;
        }
    }
    return false;
}

/**
 * 移除插入的节点
 * @param {Array} coord 
 */
Route.prototype.removeVertice = function (coord) {
    var key = this._keyFn(roundCoord(coord, this._precision));
    if (this._graph.vertices[key]) {
        var index = 0;
        var key1,key2;
        for (const subKey in this._graph.vertices[key]) {
            if (this._graph.vertices[subKey]) {
                delete this._graph.vertices[subKey][key];
            }
            if (index == 0) {
                key1 = subKey;
            }
            else
            {
                key2 = subKey;
            }
            index ++;
        }
        var coord1 = this._graph.sourceVertices[key1],coord2 = this._graph.sourceVertices[key2];
        var weight = this._weightFn(coord1, coord2);
        this._graph.vertices[key1][key2] = weight;
        this._graph.vertices[key2][key1] = weight;
        delete this._graph.vertices[key];
    }
    if (this._graph.sourceVertices[key]) {
        delete this._graph.sourceVertices[key];
    }
}

/**
 * 将起始点加入关键节点
 * @param {*} n 
 * @returns 
 */
Route.prototype.createPhantom = function (n) {

    if (this._graph.compactedVertices[n]) return null;
    var phantom = this.compactor.compactNode(n, this._graph.vertices, this._graph.compactedVertices, this._graph.sourceVertices, this._graph.edgeData, true, this._options);
    this._graph.compactedVertices[n] = phantom.edges;
    this._graph.compactedCoordinates[n] = phantom.coordinates;

    if (this._graph.compactedEdges) {
        this._graph.compactedEdges[n] = phantom.reducedEdges;
    }

    Object.keys(phantom.incomingEdges).forEach(function (neighbor) {
        this._graph.compactedVertices[neighbor][n] = phantom.incomingEdges[neighbor];
        this._graph.compactedCoordinates[neighbor][n] = phantom.incomingCoordinates[neighbor];
        if (this._graph.compactedEdges) {
            this._graph.compactedEdges[neighbor][n] = phantom.reducedEdges[neighbor];
        }
    }.bind(this));

    return n;
}

/**
 * 将起始点移除关键节点
 * @param {*} n 
 * @returns 
 */
Route.prototype.removePhantom = function (n) {
    if (!n) return;

    Object.keys(this._graph.compactedVertices[n]).forEach(function (neighbor) {
        delete this._graph.compactedVertices[neighbor][n];
    }.bind(this));
    Object.keys(this._graph.compactedCoordinates[n]).forEach(function (neighbor) {
        delete this._graph.compactedCoordinates[neighbor][n];
    }.bind(this));
    if (this._graph.compactedEdges) {
        Object.keys(this._graph.compactedEdges[n]).forEach(function (neighbor) {
            delete this._graph.compactedEdges[neighbor][n];
        }.bind(this));
    }

    delete this._graph.compactedVertices[n];
    delete this._graph.compactedCoordinates[n];

    if (this._graph.compactedEdges) {
        delete this._graph.compactedEdges[n];
    }
}


/**
 * geojson数据预处理
 * @param {*} graph 
 * @param {*} options 
 */
Route.prototype.prepare = function (graph, options) {
    options = options || {};

    var topo;

    if (graph.type === 'FeatureCollection') {
        // Graph is GeoJSON data, create a topology from it
        topo = this.topology(graph, options);
    } else if (graph.edges) {
        // Graph is a preprocessed topology
        topo = graph;
    }
    var that = this;
    var graph = topo.edges.reduce(function buildGraph(g, edge, i, es) {
        var a = edge[0],
            b = edge[1],
            props = edge[2],
            w = that._weightFn(topo.vertices[a], topo.vertices[b], props),
            makeEdgeList = function makeEdgeList(node) {
                if (!g.vertices[node]) {
                    g.vertices[node] = {};
                    if (options.edgeDataReduceFn) {
                        g.edgeData[node] = {};
                    }
                }
            },
            concatEdge = function concatEdge(startNode, endNode, weight) {
                var v = g.vertices[startNode];
                v[endNode] = weight;
                if (options.edgeDataReduceFn) {
                    g.edgeData[startNode][endNode] = options.edgeDataReduceFn(options.edgeDataSeed, props);
                }
            };

        if (w) {
            makeEdgeList(a);
            makeEdgeList(b);
            if (w instanceof Object) {
                if (w.forward) {
                    concatEdge(a, b, w.forward);
                }
                if (w.backward) {
                    concatEdge(b, a, w.backward);
                }
            } else {
                concatEdge(a, b, w);
                concatEdge(b, a, w);
            }
        }

        if (i % 1000 === 0 && options.progress) {
            options.progress('edgeweights', i, es.length);
        }

        return g;
    }, { edgeData: {}, vertices: {} });

    var compact = this.compactor.compactGraph(graph.vertices, topo.vertices, graph.edgeData, options);

    return {
        vertices: graph.vertices,
        edgeData: graph.edgeData,
        sourceVertices: topo.vertices,
        compactedVertices: compact.graph,
        compactedCoordinates: compact.coordinates,
        compactedEdges: options.edgeDataReduceFn ? compact.reducedEdges : null
    };
}

/**
 * 建立geojson的拓扑关系，主要是提取出顶点和边
 * @param {*} geojson 
 * @param {*} options 
 * @returns 
 */
Route.prototype.topology = function (geojson, options) {
    options = options || {};
    var that = this;
    var lineStrings = geoJsonFilterFeatures(geojson, isLineString);
    var explodedLineStrings = turf.explode(lineStrings);
    var vertices = explodedLineStrings.features.reduce(function buildTopologyVertices(cs, f, i, fs) {
        var rc = roundCoord(f.geometry.coordinates, that._precision);
        cs[that._keyFn(rc)] = f.geometry.coordinates;

        if (i % 1000 === 0 && options.progress) {
            options.progress('topo:vertices', i, fs.length);
        }

        return cs;
    }, {});
    var edges = geoJsonReduce(lineStrings, function buildTopologyEdges(es, f, i, fs) {
        f.geometry.coordinates.forEach(function buildLineStringEdges(c, i, cs) {
            if (i > 0) {
                var k1 = that._keyFn(roundCoord(cs[i - 1], that._precision)),
                    k2 = that._keyFn(roundCoord(c, that._precision));
                es.push([k1, k2, f.properties]);
            }
        });

        if (i % 1000 === 0 && options.progress) {
            options.progress('topo:edges', i, fs.length);
        }
        return es;
    }, []);

    return {
        vertices: vertices,
        edges: edges
    };
}

/**
 * 压缩工具，简化网络，去除网络中间的节点
 * @returns 
 */
Route.prototype.compactor = {

    findNextEnd: function (prev, v, vertices, ends, vertexCoords, edgeData, trackIncoming, options) {
        var weight = vertices[prev][v],
            reverseWeight = vertices[v][prev],
            coordinates = [],
            path = [],
            reducedEdge = options.edgeDataSeed;

        if (options.edgeDataReduceFn) {
            reducedEdge = options.edgeDataReduceFn(reducedEdge, edgeData[v][prev]);
        }

        while (!ends[v]) {
            var edges = vertices[v];

            if (!edges) { break; }

            var next = Object.keys(edges).filter(function notPrevious(k) { return k !== prev; })[0];
            weight += edges[next];

            if (trackIncoming) {
                reverseWeight += vertices[next][v];

                if (path.indexOf(v) >= 0) {
                    ends[v] = vertices[v];
                    break;
                }
                path.push(v);
            }

            if (options.edgeDataReduceFn) {
                reducedEdge = options.edgeDataReduceFn(reducedEdge, edgeData[v][next]);
            }

            coordinates.push(vertexCoords[v]);
            prev = v;
            v = next;
        }

        return {
            vertex: v,
            weight: weight,
            reverseWeight: reverseWeight,
            coordinates: coordinates,
            reducedEdge: reducedEdge
        };
    },

    compactNode: function (k, vertices, ends, vertexCoords, edgeData, trackIncoming, options) {
        options = options || {};
        var neighbors = vertices[k];
        var that = this;
        return Object.keys(neighbors).reduce(function compactEdge(result, j) {
            var neighbor = that.findNextEnd(k, j, vertices, ends, vertexCoords, edgeData, trackIncoming, options);
            var weight = neighbor.weight;
            var reverseWeight = neighbor.reverseWeight;
            if (neighbor.vertex !== k) {
                if (!result.edges[neighbor.vertex] || result.edges[neighbor.vertex] > weight) {
                    result.edges[neighbor.vertex] = weight;
                    result.coordinates[neighbor.vertex] = [vertexCoords[k]].concat(neighbor.coordinates);
                    result.reducedEdges[neighbor.vertex] = neighbor.reducedEdge;
                }
                if (trackIncoming &&
                    !isNaN(reverseWeight) && (!result.incomingEdges[neighbor.vertex] || result.incomingEdges[neighbor.vertex] > reverseWeight)) {
                    result.incomingEdges[neighbor.vertex] = reverseWeight;
                    var coordinates = neighbor.coordinates;
                    coordinates.reverse();
                    coordinates = [vertexCoords[neighbor.vertex]].concat(neighbor.coordinates);
                    result.incomingCoordinates[neighbor.vertex] = coordinates;
                }
            }
            return result;
        }, { edges: {}, incomingEdges: {}, coordinates: {}, incomingCoordinates: {}, reducedEdges: {} });
    },

    compactGraph: function (vertices, vertexCoords, edgeData, options) {
        options = options || {};
        var progress = options.progress;
        var ends = Object.keys(vertices).reduce(function findEnds(es, k, i, vs) {
            var vertex = vertices[k];
            var edges = Object.keys(vertex);
            var numberEdges = edges.length;
            var remove;

            if (options.compact !== undefined && !options.compact) {
                remove = false;
            } else if (numberEdges === 1) {
                var other = vertices[edges[0]];
                remove = !other[k];
            } else if (numberEdges === 2) {
                remove = edges.filter(function (n) {
                    return vertices[n][k];
                }).length === numberEdges;
            } else {
                remove = false;
            }

            if (!remove) {
                es[k] = vertex;
            }

            if (i % 1000 === 0 && progress) {
                progress('compact:ends', i, vs.length);
            }

            return es;
        }, {});
        var that = this;
        return Object.keys(ends).reduce(function compactEnd(result, k, i, es) {
            var compacted = that.compactNode(k, vertices, ends, vertexCoords, edgeData, false, options);
            result.graph[k] = compacted.edges;
            result.coordinates[k] = compacted.coordinates;

            if (options.edgeDataReduceFn) {
                result.reducedEdges[k] = compacted.reducedEdges;
            }

            if (i % 1000 === 0 && progress) {
                progress('compact:nodes', i, es.length);
            }

            return result;
        }, { graph: {}, coordinates: {}, reducedEdges: {} });
    }
}

/**
 * Dijkstra最短路径计算
 * @param {*} graph 
 * @param {*} start 
 * @param {*} end 
 * @returns 
 */
Route.prototype.dijkstraCalc = function (graph, start, end) {
    var costs = {};
    costs[start] = 0;
    var initialState = [0, [start], start];
    var queue = new TinyQueue([initialState], function (a, b) { return a[0] - b[0]; });
    var explored = {};

    while (queue.length) {
        var state = queue.pop();
        var cost = state[0];
        var node = state[2];
        if (node === end) {
            return state.slice(0, 2);
        }

        var neighbours = graph[node];
        Object.keys(neighbours).forEach(function (n) {
            var newCost = cost + neighbours[n];
            if (!(n in costs) || newCost < costs[n]) {
                costs[n] = newCost;
                var newState = [newCost, state[1].concat([n]), n];
                queue.push(newState);
            }
        });
    }

    return null;
}


/**
 * 对geojson做reduce处理
 * @param {*} geojson 
 * @param {*} fn 
 * @param {*} seed 
 * @returns 
 */
function geoJsonReduce(geojson, fn, seed) {
    if (geojson.type === 'FeatureCollection') {
        return geojson.features.reduce(function reduceFeatures(a, f) {
            return geoJsonReduce(f, fn, a);
        }, seed);
    } else {
        return fn(seed, geojson);
    }
}

/**
 * 根据条件函数搜索geojson中的要素
 * @param {*} geojson 
 * @param {*} fn 
 * @returns 
 */
function geoJsonFilterFeatures(geojson, fn) {
    var features = [];
    if (geojson.type === 'FeatureCollection') {
        features = features.concat(geojson.features.filter(fn));
    }

    return {
        type: 'FeatureCollection',
        features: features
    };
}

/**
 * 是否是LineString
 * @param {*} f 
 * @returns 
 */
function isLineString(f) {
    return f.geometry.type === 'LineString';
}

/**
 * 坐标保留小数位
 * @param {*} c 
 * @param {*} precision 
 * @returns 
 */
function roundCoord(c, precision) {
    // return [
    //     Math.round(c[0] / precision) * precision,
    //     Math.round(c[1] / precision) * precision,
    // ];

    return [
        c[0].toFixed(precision),
        c[1].toFixed(precision),
    ];
}
